1. Field of the Invention
The present invention relates in general to the field of information processing, and more specifically to a system and method for prioritizing configuration using a combined configuration-attribute data model.
2. Description of the Related Art
Computer assisted product configuration continues to offer substantial benefits to a wide range of users and industries. FIG. 1 depicts a conventional product configuration process 100 performed by a configuration engine 101. The configuration process 100 represents one embodiment of an inference procedure. In one embodiment of a conventional inference procedure, configuration query 102 is formulated based on user configuration input, a configuration engine performs the configuration query 102 using a configuration model 104, and the configuration engine provides an answer 106 to the configuration query 102 based on the configuration query 102 and the contents of the configuration model 104. The answer 106 represents a particular response to the configuration query 102.
A configuration model 104 uses, for example, data, rules, and/or constraints (collectively referred to as “data”) to define compatibility relationships between parts (also commonly referred to as “features”) contained in a specific type of product. A part represents a single component or attribute from a larger, more complex system. Parts may be combined in different ways in accordance with rules and/or constraints to define different instances of the more complex system. For example, “V6 engine” or the exterior color “red” can be parts on a vehicle, and a specific hard disk drive can be a part on a computer. A part group, also called a group or family, represents a collection of related parts. For example, an “Engines” group might contain the parts “V6 engine” and “4 cylinder engine”. A product configuration is a set of parts that define a product. For example, a vehicle configuration containing the parts “V6 engine” and “red” represents a physical vehicle that has a red exterior and a V6 engine. A product can be a physical product such as a vehicle, computer, or any other product that consists of a number of configurable features such as an insurance product. Additionally, a product can also represent a service such as financial services, insurance services, or consulting services.
An attribute represents a particular detail about a part or part group. Attributes describe details about the part or part group. A single part or part group can have many attributes. For example, the part “V6 engine” might have a price attribute of “$500”, a weight attribute of “1,000 lbs” and a description attribute of “Six cylinder gas engine.” Also, an attribute for a given part or part group may change depending on context (what other parts or attributes are present). For example, the price attribute for the “V6 engine” might be “$500” when the “XLT trim” part is present and the price attribute for the “V6 Engine” might be “$800” when the “XL trim” part is present.
A configuration query (also referred to as a “query”) is essentially a question that is asked about the parts, relationships, and attributes in a configuration model. The answer returned from a configuration query will depend on the data in the configuration model, the approach used for answering the question, and the specifics of the question itself. For example, one possible configuration query, translated to an English sentence, is the following: For the given configuration model, are the parts “red” and “V6 engine” compatible with each other? Another possible configuration query is the following: For the given configuration model, is the “V6 engine” part standard or optional when in the presence of the “XLT trim”, “XL trim”, “USA”, and “Canada” parts, wherein “standard” and “optional” are attributes?
The configuration model 104 can be used to determine, for example, which parts are compatible with other parts, and provide additional details around specific relationships. For example, a vehicle configuration model can indicate that “red” (a part) is the standard feature from the color part group for a specific vehicle and “red” is not compatible with “V6 engine” (a part). Configuration model 104 may also contain additional information needed to support specific product related queries. Configuration models can be developed in any number of ways. U.S. Pat. No. 5,825,651 entitled “Method and Apparatus for Maintaining and Configuring Systems”, inventors Gupta et al., and assigned to Trilogy Development Group, Inc., describes an example configuration engine and rules based configuration model. U.S. Pat. No. 5,825,651 (referred to herein as the “Gupta Patent”) is incorporated herein by reference in its entirety. U.S. Pat. No. 5,515,524 entitled “Method and Apparatus for Configuring Systems”, inventors John Lynch and David Franke, and assigned to Trilogy Development Group, Inc., describes another example configuration engine and constraint based configuration model. U.S. Pat. No. 5,515,524 (referred to herein as the “Lynch Patent”) is also incorporated by reference in it entirety.
FIG. 2 depicts an example configuration model 200 of a product represented in a graphical, tree based form. The product can be configured to include part combinations A1, B1 or B2, C1, X1 or X2, and Y1 or configured to include part combinations A2, B2, C2, X2, and Y1 or Y2. The configuration model 200 includes rules to define these part relationships. Table 1 represents an example rule set, wherein “S” represents “standard” and “O” represents optional. Configuration model 200 represents a relatively non-complex configuration model. Actual configuration models for a single product can include hundreds of thousands or more parts, rules, and attributes.
TABLE 1Example Configuration Rules for a ProductA1 S ALLA2 O ALLB1 S A1B2 S A2B2 O A1C1 S A1C2 S A2X1 S C1X2 S C2X2 O C1Y1 S C1Y1 S C2Y2 O C2
Many configuration queries are formulated with respect to attribute values. Such processing is referred to herein as “attribute-based configuration” Attributes can (1) be used to find “preferred” answers to configuration queries (such queries are referred to herein as “attribute-prioritized queries”), (2) be an output of a configuration query (such queries are referred to herein as “attribute queries”), and (3) be used in a query that is both an attribute-prioritized query and an attribute query. An example of an attribute-prioritized query is the following: “Given a set of configured parts, return the part with the lowest cost that is compatible with the given parts, according to the rules in a given configuration model”. An example of an attribute query is the following: “Given a configuration model and a fully specified configuration, determine the sum of the price attributes for all of the parts in that configuration.” Attribute-based configuration processing has conventionally suffered from scale and performance issues, an example of which is described below.
Example: A Conventional Approach to Attribute-Prioritized Solutions
When more than one answer to a configuration query is valid, the attributes of each configuration answer can be used to assign a preference weighting to the valid answers. For example, there may be many answers that satisfy the configuration query of “Add parts to the list of ‘red’ and ‘V6 engine’ until a complete vehicle is specified.” However, attribute values can be used to identify preferred valid answers such as the least expensive vehicle, the most expensive vehicle, the heaviest vehicle, etc.
FIG. 3 depicts a conventional attribute based priority configuration system 300 (also referred to as a “conventional attribute based priority configuration engine”), and FIG. 4 depicts a conventional attribute based priority solution process 400 to determine an attribute based priority solution. Client systems 301(1) through 301(n) access the conventional attribute based priority solution system 300 via a network 302, such as the Internet. The system 300 and process 400 are typically implemented configured as a server computer system.
Conventionally, a configuration model 304 is driven solely by configuration rules 306. Thus, in operation 402, configuration rules 306 are manipulated to form a configuration model 304 that is capable of answering configuration questions. The configuration model 304 is separated from attribute information 308 and, thus, the configuration model 304 is not used to process attribute related data. In operation 404, the conventional attribute based priority solution process 400 answers an attribute specific configuration query 310 to determine an attribute based priority solution by querying configuration model 304 for the set of valid answers 312. The valid answers 312 represent product configurations that conform to the configuration model 304. Operation 404 interrogates the configuration model 304 to find the preferred answer from the set of valid answers. Operation 406 then applies attribute information 308 to the valid answers 312 to associate each valid answer with the attributes that apply to the valid answer. A weight can be derived from the applied attribute information 308 to generate weighted answers 314. For example, for the attributes “standard” and “optional”, the weight can be the total number of standard features or the total number optional features in each answer. Operation 408 uses a preference algorithm 316, e.g. search for the valid answer with the most standard features and lowest price, to select the preferred valid answer 318 given the weighted valid answers. The particular preference algorithm is a matter of system usage. Once a preferred answer is selected, conventional attribute based priority solution process 400 can determine answers for the next configuration query.
A software application developed by Trilogy Development Group, Inc. and referred to as “MCC Config” implemented the conventional attribute based priority configuration system 300 using a modified attribute based priority solution process 400. MCC Config solved a configuration problem by taking partial configuration answers as input data and, over iterative processes, provided a complete configuration output. The modified process was an iterative process that created a single, preferred complete configuration over multiple iterations, rather than providing all valid complete configurations and choosing a preferred one. For each iteration the configuration model 304 provided a set of part selections. The set of part selections formed a subset of all of the part selections that needed to be made to generate a preferred, complete configuration. The modified process then used the attribute information 308 and the preference algorithm 316 to make the part selections provided by the configuration model 304. Part selections answers were then fed back into the configuration model 304 and added to the partial configuration answers. The partial configuration answers were then used by the configuration model 304 to generate the next set of part selections that needed to be made, and so on until the configuration was completed. For example, in an automotive configuration context, a user could initially select: engine=V6 and color=red. The configuration engine could determine that, for example, 2 different transmissions and 6 different body styles were compatible with engine=V6 and color=red. The modified process would then select a transmission and body style from the set of transmissions and body styles provided according to the preference algorithm 316. If “standard” was the controlling preference in the preference algorithm 316, the modified process would select the standard transmission and body style, if possible, from the available choices. The selected transmission and body style would then be added to the initial user selections and the process would repeat until a complete configuration was attained.
Process 400 exhibits the drawback of expending effort to determine valid answers that will eventually be ignored if they are not preferred by the attribute model. Also, the number of valid answers can be so large that calculating the full set and identifying the preferred answer is often computationally infeasible.